package ustc.xiaoyang.karl.binarysearch;

import java.util.Arrays;

public class FindTheFirstAndLastPosition34 {
    public static void main(String[] args) {

        int [] nums = {5,7,7,8,8,10};
        System.out.println(Arrays.toString(new FindTheFirstAndLastPosition34().searchRange(nums, 8)));
    }
    public int[] searchRange(int[] nums,int target){
        int left = leftBound(nums,target);
        int right = rightBound(nums,target);
        return new int[]{left, right};
    }

    //寻找左边界
    public int leftBound(int[] nums,int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + right >> 1;
            if(nums[mid] >= target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        if (left >= nums.length || nums[left] != target){
            return -1;
        }
        return left;
    }
    //寻找右边界
    public int rightBound(int[] nums,int target){
        int left = 0, right = nums.length - 1;
        while(left <= right){
            int mid = left + (right-left >> 1);
            if(nums[mid] <= target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        if(right < 0 || nums[right] != target)
            return -1;
        return right;
    }

}
